#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
typedef struct ListNode
{
	int val;
	struct ListNode* next;
}ListNode;

struct ListNode* list(struct ListNode* head, int val)
{
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	ListNode* LessHead, *LessTail, *strongHead, *strongTail;
	LessHead = LessTail = (ListNode*)malloc(sizeof(ListNode));
	LessTail->next = NULL;
	strongHead = strongTail = (ListNode*)malloc(sizeof(ListNode));
	strongTail->next = NULL;
	ListNode* pcur = head;
	while (pcur)
	{
		if (pcur->val < val)
		{
			LessTail->next = pcur;
			LessTail = LessTail->next;
			pcur = pcur->next;
		}
		else
		{
			strongTail->next = pcur;
			strongTail = strongTail->next;
			pcur = pcur->next;
		}
	}
	LessTail->next = strongHead->next;
	strongTail->next = NULL;
	ListNode* ret = LessHead->next;
	free(LessHead);
	free(strongHead);
	return ret;
}